The Viterbi decoder or the Viterbi decoding algorithm are widely used for efficient coding in digital communication systems. The Viterbi decoder performs maximum likelihood decoding and involves calculating a measure of similarity or distance between the received signal and all the code trellis paths entering each state. The Viterbi algorithm removes trellis paths that are not likely to be candidates for the maximum likelihood choices. Therefore, the Viterbi aims to choose the code word with the maximum likelihood metric or stated another way, the code word with the minimum distance metric. The computation involves accumulating the distance metrics along a path using a perfect integrator.
Referring to FIG. 1, a Viterbi decoder circuit or algorithm portion 10 includes distance calculators 12-1, 12-2, to 12-N which compute the distance or difference of the received symbol from expected symbols 1 through N. The resultant computed distance from each calculator is then summed with the previous sum. The perfect integrator essentially implements an infinite accumulation for an infinite number of bits. Because a realistic implementation has a finite amount of memory and resources, the resultant accumulated sum inevitably overflows which is a condition know as saturation. When saturation occurs, the solution becomes corrupted and useless. Therefore, it is a requirement of every Viterbi decoder or decoding algorithm to protect against saturation.
Conventional anti-saturation solutions check each accumulated sum at each iteration (blocks 20-1, 20-2, and 20-N) to determine whether the accumulated sum is about to overflow. If yes, the metrics are scaled down by the same value to avoid saturation (blocks 26-1, 26-2, and 26-N). An alternative conventional method involves scaling or normalizing all metrics for every input symbol so that the most likely metric is always zero. Yet a third conventional method uses floating point implementation rather than fixed point implementation.
All the above-mentioned anti-saturation techniques suffer from several undesirable disadvantages. These conventional methods slow down the computation speed, use more hardware in the implementation, are more costly, and use more power to operate. Further, the floating point implementation is still at risk for saturation albeit at a decrease rate than the fixed point implementation.